// 非递归的快速排序用栈来实现
function quickSort1(arr, left, right) {
  const stack = [
    [left, right]
  ];
  while (stack.length > 0) {
    // 利用解构取出栈中的一个数组元素的两个值
    let [i, j] = stack.shift();
    if (i >= j) {
      continue;
    }
    // 把起始位置保存下来
    let start = i;
    let end = j;
    // 把开始位置的值作为比较的目标
    let pivot = arr[start];
    while (i < j) {
      while (i < j && arr[j] >= pivot) {
        j--;
      }
      while (i < j && arr[i] <= pivot) {
        i++;
      }
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
    [arr[start], arr[i]] = [arr[i], arr[start]];

    stack.push([start, i - 1]);
    stack.push([i + 1, end]);
  }
}

arr1 = [9, 8, 4, 6, 5, 1];
quickSort1(arr1, 0, arr1.length - 1);
console.log(arr1);